package xml和xsd的校验;

public class test {
    public static void main(String[] args) {
        int[][] heights = {{1,2,2},{3,8,2},{5,3,5}};
        test t = new test();
        t.minimumEffortPath(heights);
    }

    int[][] w;
    public int minimumEffortPath(int[][] heights) {
        int x = heights.length;
        int y = heights[0].length;
        w = new int[x][y];
        for (int i = 0;i<x;i++){
            for (int j = 0; j < y; j++) {
                w[i][j] = Integer.MAX_VALUE;
            }
        }
        w[0][0] = 0;
        dms(heights,0,0);

        return w[x][y];
    }

    private void dms(int[][] heights,int x,int y) {

        int d = 0;
        if(x-1>=0){
            d = Math.abs(heights[x][y]-heights[x-1][y]);
            if(d<w[x-1][y]){
                if(d>w[x][y]){
                    w[x-1][y] = d;
                }else {
                    w[x-1][y] = w[x][y];
                }
                dms(heights,x-1,y);
            }
        }
        if(x+1<heights.length){
            d = Math.abs(heights[x][y]-heights[x+1][y]);
            if(d<w[x+1][y]){
                if(d>w[x][y]){
                    w[x+1][y] = d;
                }else {
                    w[x+1][y] = w[x][y];
                }
                dms(heights,x+1,y);
            }
        }
        if(y-1>=0){
            d = Math.abs(heights[x][y]-heights[x][y-1]);
            if(d<w[x][y-1]){
                if(d>w[x][y]){
                    w[x][y-1] = d;
                }else {
                    w[x][y-1] = w[x][y];
                }
                dms(heights,x,y-1);
            }
        }
        if(y+1<heights[0].length){
            d = Math.abs(heights[x][y]-heights[x][y+1]);
            if(d<w[x][y+1]){

                if(d>w[x][y]){
                    w[x][y+1] = d;
                }else {
                    w[x][y+1] = w[x][y];
                }
                dms(heights,x,y+1);
            }
        }

    }

}
